#include <iostream>
using namespace std;
int n, a, b, c = 0, book[500] = {0},x[500] ;//定义全局变量 
void payback(int i)//使用回溯算法支付
{
 if(b < a)
 {
  while(i <= n)
  {   
   if(!book[i])
   {
    book[i] = 1;
    b += x[i];
    payback(i + 1);//递归调用自己 
    book[i] = 0;
    b -= x[i];    
   }
   ++i;
  }
 }
 else if(b == a) 
 {
 int d;
 int flag =false;
 for(int i = 1; i <= n; ++i)//时间复杂度为O（n） 
 {
  if(book[i])            //输出支付的钱 
  {
   if(flag) putchar(' ');
   printf("%d", x[i]);       
   flag = true; 
   
   d++; 
  } 
 }
 putchar('\n');
 ++c;
 printf("%d",d);  
} 
}

int main()
{
 printf("不同面值的钱的种类数为："); //输入不同面值的钱的种类数 
 scanf("%d", &n);                   
 printf("请输入不同面值的钱的大小");//输入各面值的钱 
 for(int i = 1; i <= n; ++i) scanf("%d", &x[i]); 
 printf("输入要支付的钱"); //输入你要支付的钱
 scanf("%d", &a);  
 payback(1);              //调用函数得出支付方法 
 if(c == 0) printf("很抱歉不能支付\n"); //不能支付 
 return 0; 
} 
